|
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph, or set of vertices connected by edges, where the edges have a direction associated with them. In formal terms, a directed graph is an ordered pair (sometimes ) with〔. , Section 1.10. , Section 10.〕 * ''V'' a set whose elements are called ''vertices'', ''nodes'', or ''points''; * ''A'' a set of ordered pairs of vertices, called ''arrows'', ''directed edges'' (sometimes simply ''edges'' with the corresponding set named ''E'' instead of ''A''), ''directed arcs'', or ''directed lines''. It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called ''edges'', ''arcs'', or ''lines''. A directed graph is called a ''simple graph'' if it has no multiple arrows (two or more edges that connect the same two vertices) and no loops (edges that connect vertices to themselves). A directed graph is called a ''multigraph'' or ''multidigraph'' if it may have multiple arrows (and sometimes loops). In the latter case the arrow set forms a multiset, rather than a set, of ordered pairs of vertices. ==Basic terminology== An arrow is considered to be directed ''from'' ''x'' ''to'' ''y''; ''y'' is called the ''head'' and ''x'' is called the ''tail'' of the arrow; ''y'' is said to be a ''direct successor'' of ''x'' and ''x'' is said to be a ''direct predecessor'' of ''y''. If a path leads from ''x'' to ''y'', then ''y'' is said to be a ''successor'' of ''x'' and ''reachable'' from ''x'', and ''x'' is said to be a ''predecessor'' of ''y''. The arrow is called the ''inverted arrow'' of . An orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. Any directed graph constructed this way is called an ''oriented graph''. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of and may be arrows of the graph).〔, Section 1.10.〕 A ''weighted directed graph'' is a directed graph with weights assigned to its arrows, similar to a weighted graph. In the context of graph theory, a weighted directed graph is called a ''network''. The adjacency matrix of a multidigraph with loops is the integer-valued matrix with rows and columns corresponding to the vertices, where a nondiagonal entry ''a''''ij'' is the number of arrows from vertex ''i'' to vertex ''j'', and the diagonal entry ''a''''ii'' is the number of loops at vertex ''i''. The adjacency matrix of a directed graph is unique up to identical permutation of rows and columns. Another matrix representation for a directed graph is its incidence matrix. See direction for more definitions. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Directed graph」の詳細全文を読む スポンサード リンク
|